package gdut.edu.demo04;

import gdut.edu.demo02.MyQueue;

import java.util.Arrays;

/**
 * @Description 基数排序基于队列实现
 * @Author JiaFu
 * @Date 2022/11/11 20:40
 */
public class RadixQueueSort {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 12, 345, 56, 765, 33, 22, 12, 7, 889, 0};
        radixQueueSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixQueueSort(int[] arr) {
        //数组中最大数字
        int max = Integer.MIN_VALUE;
        //找出数组中最大数字
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //存放临时数据的队列数组
        MyQueue[] queueArr = new MyQueue[10];
        for (int i = 0; i < queueArr.length; i++) {
            queueArr[i] = new MyQueue();
        }
        //最大数字的位数
        int maxLength = (max + "").length();
        //根据最大长度决定比较次数
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //把每个数字计算余数
            for (int j = 0; j < arr.length; j++) {
                //计算余数
                int ys = (arr[j] / n) % 10;
                //将数据存入相应的存放临时数据的队列中
                queueArr[ys].add(arr[j]);
            }
            //记录取出临时数据存放到原数组的位置
            int index = 0;
            //将临时数据按照一定顺序取出存放到原来的数组
            for (int j = 0; j < queueArr.length; j++) {
                MyQueue queue = queueArr[j];
                while (!queue.isEmpty()) {
                    arr[index] = queue.poll();
                    index++;
                }
            }
        }
    }
}
